#include<iostream>
#include<algorithm>
#include<map>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 510;
int n, k;
LL f[50];
int main()
{
	/*int cnt = 0;
	f[1] = 0, f[2] = 1;
	for (int i = 3; i <= 50; i++) {
		f[i] = f[i - 1] + f[i - 2];
		cnt++;
		if (f[i] > 1e9)break;
	}
	cout << cnt << endl;*/
	int t;
	cin >> t;
	while (t--) {
		cin >> n >> k;
		k = min(k, 44);
		int cnt = 0;
		int idx = n;
		while (idx != 0) {
			memset(f, 0, sizeof(f));
			f[k] = n;
			f[k - 1] = idx;
			bool flag = 0;
			for (int i = k - 2; i >= 1; i--) {
				f[i] = f[i + 2] - f[i + 1];
				//cout<<"f[i]=="<<f[i]<<endl;
				if (f[i] < 0) {
					flag = 1;
					break;
				}
				if (f[i] == 0 && i != 1) {
					flag = 1;
					break;
				}
				if (f[i] > f[i + 1]) {
					flag = 1;
					break;
				}
			}
			if (!flag) {
				cnt++;
				// for(int i=1;i<=k;i++){
				//     cout<<"f[i]=="<<f[i]<<endl;
				// }
			}
			idx--;
		}
		cout << cnt << endl;
	}
	return 0;
}
